SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Viterbi algorithm</title>

</head>

Viterbi algorithm

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

The Viterbi algorithm is a <a href="Dynamic_programming" title="Dynamic programming">dynamic programming</a> <a href="Algorithm" title="Algorithm">algorithm</a> that finds the most likely sequence of hidden events that would explain a sequence of observed events. The result of the algorithm is often called the Viterbi path. It is most commonly used with <a href="Hidden_Markov_model" title="Hidden Markov model">hidden Markov models</a> (HMMs). For example, if a doctor observes a patient's symptoms over several days (the observed events), the Viterbi algorithm could determine the most probable sequence of underlying health conditions (the hidden events) that caused those symptoms.

The algorithm has found universal application in decoding the <a href="Convolutional_code" title="Convolutional code">convolutional codes</a> used in both <a href="Code-division_multiple_access" title="Code-division multiple access">CDMA</a> and <a href="GSM" title="GSM">GSM</a> digital cellular, <a href="Dial-up_Internet_access" title="Dial-up Internet access">dial-up</a> modems, satellite, deep-space communications, and <a href="802.11" class="mw-redirect" title="802.11">802.11</a> wireless LANs. It is also commonly used in <a href="Speech_recognition" title="Speech recognition">speech recognition</a>, <a href="Speech_synthesis" title="Speech synthesis">speech synthesis</a>, <a href="Speaker_diarisation" title="Speaker diarisation">diarization</a>,<a href="#cite_note-1">[1]</a> <a href="Keyword_spotting" title="Keyword spotting">keyword spotting</a>, <a href="Computational_linguistics" title="Computational linguistics">computational linguistics</a>, and <a href="Bioinformatics" title="Bioinformatics">bioinformatics</a>. For instance, in <a href="Speech-to-text" class="mw-redirect" title="Speech-to-text">speech-to-text</a> (speech recognition), the acoustic signal is the observed sequence, and a string of text is the "hidden cause" of that signal. The Viterbi algorithm finds the most likely string of text given the acoustic signal.

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

The Viterbi algorithm is named after <a href="Andrew_Viterbi" title="Andrew Viterbi">Andrew Viterbi</a>, who proposed it in 1967 as a decoding algorithm for <a href="Convolution_code" class="mw-redirect" title="Convolution code">convolutional codes</a> over noisy digital communication links.<a href="#cite_note-2">[2]</a> It has, however, a history of <a href="Multiple_invention" class="mw-redirect" title="Multiple invention">multiple invention</a>, with at least seven independent discoveries, including those by Viterbi, <a href="Needleman%E2%80%93Wunsch_algorithm" title="Needleman–Wunsch algorithm">Needleman and Wunsch</a>, and <a href="Wagner%E2%80%93Fischer_algorithm" title="Wagner–Fischer algorithm">Wagner and Fischer</a>.<a href="#cite_note-slp-3">[3]</a> It was introduced to <a href="Natural_language_processing" title="Natural language processing">natural language processing</a> as a method of <a href="Part-of-speech_tagging" title="Part-of-speech tagging">part-of-speech tagging</a> as early as 1987.

Viterbi path and Viterbi algorithm have become standard terms for the application of dynamic programming algorithms to maximization problems involving probabilities.<a href="#cite_note-slp-3">[3]</a>

For example, in statistical parsing a dynamic programming algorithm can be used to discover the single most likely context-free derivation (parse) of a string, which is commonly called the "Viterbi parse".<a href="#cite_note-4">[4]</a><a href="#cite_note-5">[5]</a><a href="#cite_note-6">[6]</a> Another application is in <a href="Optical_motion_tracking" class="mw-redirect" title="Optical motion tracking">target tracking</a>, where the track is computed that assigns a maximum likelihood to a sequence of observations.<a href="#cite_note-7">[7]</a>

<div class="mw-heading mw-heading2"><h2 id="Algorithm">Algorithm</h2></div>

Given a hidden Markov model with a set of hidden states <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math><img src="./4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"> and a sequence of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> observations <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o_{0},o_{1},\dots ,o_{T-1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o_{0},o_{1},\dots ,o_{T-1}}</annotation>

</semantics>

</math><img src="./961b37470ba672ddf5c8f0aa86bf23d80ca1fb63.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:15.193ex; height:2.009ex;" alt="{\displaystyle o_{0},o_{1},\dots ,o_{T-1}}" loading="lazy">, the Viterbi algorithm finds the most likely sequence of states that could have produced those observations. At each time step <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

</math><img src="./65658b7b223af9e1acc877d848888ecdb4466560.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.84ex; height:2.009ex;" alt="{\displaystyle t}" loading="lazy">, the algorithm solves the subproblem where only the observations up to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o_{t}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o_{t}}</annotation>

</semantics>

</math><img src="./3cd2cf4bfdabc8ae396ce3fa32aeb871efb3d732.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.954ex; height:2.009ex;" alt="{\displaystyle o_{t}}" loading="lazy"> are considered.

Two matrices of size <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T\times \left|{S}\right|}">

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T\times \left|{S}\right|}</annotation>

</semantics>

</math><img src="./503991e6d34c90301bfef089b6f8da94d8c27a46.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.27ex; height:2.843ex;" alt="{\displaystyle T\times \left|{S}\right|}" loading="lazy"> are constructed:

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{t,s}}</annotation>

</semantics>

</math><img src="./2b67552369ac17012355486c518c9f0b86e7363f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.547ex; height:2.843ex;" alt="{\displaystyle P_{t,s}}" loading="lazy"> contains the maximum probability of ending up at state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> at observation <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t}</annotation>

</semantics>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{t,s}}</annotation>

</semantics>

</math><img src="./0b085c88019ace6bdd2de0aee09184a2f6947915.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.893ex; height:2.843ex;" alt="{\displaystyle Q_{t,s}}" loading="lazy"> tracks the previous state that was used before <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

Let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \pi _{s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{s}}</annotation>

</semantics>

</math><img src="./0dcfaac8814f5e62e87bca6bec267ee6e80808db.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.328ex; height:2.009ex;" alt="{\displaystyle \pi _{s}}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{r,s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{r,s}}</annotation>

</semantics>

</math><img src="./6ff41ed98ee1c232f113fb3e4197d97427ea3353.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.432ex; height:2.343ex;" alt="{\displaystyle a_{r,s}}" loading="lazy"> be the initial and transition probabilities respectively, and let <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{s,o}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{s,o}}</annotation>

</semantics>

</math><img src="./686dbe0a1403110992794769ba62210b169d6371.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.256ex; height:2.843ex;" alt="{\displaystyle b_{s,o}}" loading="lazy"> be the probability of observing <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle o}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle o}</annotation>

</semantics>

</math><img src="./0c1031f61947aa3d1cf3a70ec3e4904df2c3675d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle o}" loading="lazy"> at state <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy">. Then the values of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> are given by the recurrence relation<a href="#cite_note-8">[8]</a>

<math display="block" xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{if }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{if }}t>0.\end{cases}}}">

<msub>

</mrow>

</msub>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

</mrow>

</munder>

<mrow>

<mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

<msub>

</mrow>

</msub>

</mrow>

</msub>

</mrow>

</mrow>

</mtd>

<mtd>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P_{t,s}={\begin{cases}\pi _{s}\cdot b_{s,o_{t}}&{\text{if }}t=0,\\\max _{r\in S}\left(P_{t-1,r}\cdot a_{r,s}\cdot b_{s,o_{t}}\right)&{\text{if }}t>0.\end{cases}}}</annotation>

</semantics>

</math>

The formula for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{t,s}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{t,s}}</annotation>

</semantics>

</math><img src="./0b085c88019ace6bdd2de0aee09184a2f6947915.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:3.893ex; height:2.843ex;" alt="{\displaystyle Q_{t,s}}" loading="lazy"> is identical for <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t>0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t>0}</annotation>

</semantics>

</math><img src="./29a2960e88369263fe3cfe00ccbfeb83daee212a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.101ex; height:2.176ex;" alt="{\displaystyle t>0}" loading="lazy">, except that <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max }</annotation>

</semantics>

</math><img src="./b8e49fca3e322708b32d21eaa8b095dc05f09538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.326ex; height:1.676ex;" alt="{\displaystyle \max }" loading="lazy"> is replaced with <a href="Arg_max" title="Arg max"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \arg \max }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \arg \max }</annotation>

</semantics>

</math><img src="./6d5b88799aa6426718d91e6749b77cd6195653e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.949ex; height:2.009ex;" alt="{\displaystyle \arg \max }" loading="lazy"></a>, and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q_{0,s}=0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q_{0,s}=0}</annotation>

</semantics>

</math><img src="./789748cf1c372bd88ea0f2fe63715ef815965c06.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.382ex; height:2.843ex;" alt="{\displaystyle Q_{0,s}=0}" loading="lazy">.

The Viterbi path can be found by selecting the maximum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math><img src="./b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"> at the final timestep, and following <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Q}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q}</annotation>

</semantics>

</math><img src="./8752c7023b4b3286800fe3238271bbca681219ed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.838ex; height:2.509ex;" alt="{\displaystyle Q}" loading="lazy"> in reverse.

<div class="mw-heading mw-heading2"><h2 id="Pseudocode">Pseudocode</h2></div>

<pre>function Viterbi(states, init, trans, emit, obs) is

input states: S hidden states

input init: initial probabilities of each state

input trans: S × S transition matrix

input emit: S × O emission matrix

input obs: sequence of T observations

prob ← T × S matrix of zeroes

prev ← empty T × S matrix

for each state s in states do

prob[0][s] = init[s] * emit[s][obs[0]]

for t = 1 to T - 1 inclusive do // t = 0 has been dealt with already

for each state s in states do

for each state r in states do

new_prob ← prob[t - 1][r] * trans[r][s] * emit[s][obs[t]]

if new_prob > prob[t][s] then

prob[t][s] ← new_prob

prev[t][s] ← r

path ← empty array of length T

path[T - 1] ← the state s with maximum prob[T - 1][s]

for t = T - 2 to 0 inclusive do

path[t] ← prev[t + 1][path[t + 1]]

return path

end

</pre>

The time complexity of the algorithm is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(T\times \left|{S}\right|^{2})}">

<msup>

<mrow>

</mrow>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(T\times \left|{S}\right|^{2})}</annotation>

</semantics>

</math><img src="./beee12098b9ff184ac5fb053dc61eb322eea6b2f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.906ex; height:3.343ex;" alt="{\displaystyle O(T\times \left|{S}\right|^{2})}" loading="lazy">. If it is known which state transitions have non-zero probability, an improved bound can be found by iterating over only those <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r}</annotation>

</semantics>

</math><img src="./0d1ecb613aa2984f0576f70f86650b7c2a132538.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.049ex; height:1.676ex;" alt="{\displaystyle r}" loading="lazy"> which link to <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"> in the inner loop. Then using <a href="Amortized_analysis" title="Amortized analysis">amortized analysis</a> one can show that the complexity is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}">

<mrow>

</mrow>

</mrow>

<mrow>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}</annotation>

</semantics>

</math><img src="./3498e4e3a96ef7e9d657f31c3f7bf88aa39bec93.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:18.571ex; height:2.843ex;" alt="{\displaystyle O(T\times (\left|{S}\right|+\left|{E}\right|))}" loading="lazy">, where <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle E}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle E}</annotation>

</semantics>

</math><img src="./4232c9de2ee3eec0a9c0a19b15ab92daa6223f9b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.776ex; height:2.176ex;" alt="{\displaystyle E}" loading="lazy"> is the number of edges in the graph, i.e. the number of non-zero entries in the transition matrix.

<div class="mw-heading mw-heading2"><h2 id="Example">Example</h2></div>

A doctor wishes to determine whether patients are healthy or have a fever. The only information the doctor can obtain is by asking patients how they feel. The patients may report that they either feel normal, dizzy, or cold.

It is believed that the health condition of the patients operates as a discrete <a href="Markov_chain" title="Markov chain">Markov chain</a>. There are two states, "healthy" and "fever", but the doctor cannot observe them directly; they are hidden from the doctor. On each day, the chance that a patient tells the doctor "I feel normal", "I feel cold", or "I feel dizzy", depends only on the patient's health condition on that day.

The observations (normal, cold, dizzy) along with the hidden states (healthy, fever) form a hidden Markov model (HMM). From past experience, the probabilities of this model have been estimated as:

<pre>init = {"Healthy": 0.6, "Fever": 0.4}

trans = {

"Healthy": {"Healthy": 0.7, "Fever": 0.3},

"Fever": {"Healthy": 0.4, "Fever": 0.6},

}

emit = {

"Healthy": {"normal": 0.5, "cold": 0.4, "dizzy": 0.1},

"Fever": {"normal": 0.1, "cold": 0.3, "dizzy": 0.6},

}

</pre>

In this code, <code>init</code> represents the doctor's belief about how likely the patient is to be healthy initially. Note that the particular probability distribution used here is not the equilibrium one, which would be <code>{'Healthy': 0.57, 'Fever': 0.43}</code> according to the transition probabilities. The transition probabilities <code>trans</code> represent the change of health condition in the underlying Markov chain. In this example, a patient who is healthy today has only a 30% chance of having a fever tomorrow. The emission probabilities <code>emit</code> represent how likely each possible observation (normal, cold, or dizzy) is, given the underlying condition (healthy or fever). A patient who is healthy has a 50% chance of feeling normal; one who has a fever has a 60% chance of feeling dizzy.

A particular patient visits three days in a row, and reports feeling normal on the first day, cold on the second day, and dizzy on the third day.

Firstly, the probabilities of being healthy or having a fever on the first day are calculated. The probability that a patient will be healthy on the first day and report feeling normal is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.6\times 0.5=0.3}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0.6\times 0.5=0.3}</annotation>

</semantics>

</math><img src="./229360aa5c3fa650b28fb1e7930f0e555fbd1fd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:14.854ex; height:2.176ex;" alt="{\displaystyle 0.6\times 0.5=0.3}" loading="lazy">. Similarly, the probability that a patient will have a fever on the first day and report feeling normal is <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.4\times 0.1=0.04}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0.4\times 0.1=0.04}</annotation>

</semantics>

</math><img src="./1cf03d25171f9c6167d26ecd0a9ac8d1ca1ccc87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:16.017ex; height:2.176ex;" alt="{\displaystyle 0.4\times 0.1=0.04}" loading="lazy">.

The probabilities for each of the following days can be calculated from the previous day directly. For example, the highest chance of being healthy on the second day and reporting to be cold, following reporting being normal on the first day, is the maximum of <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.3\times 0.7\times 0.4=0.084}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0.3\times 0.7\times 0.4=0.084}</annotation>

</semantics>

</math><img src="./1e24d5c7cef810af6ee7c3a1a53d0d9bbfb67a58.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:22.991ex; height:2.176ex;" alt="{\displaystyle 0.3\times 0.7\times 0.4=0.084}" loading="lazy"> and <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0.04\times 0.4\times 0.4=0.0064}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0.04\times 0.4\times 0.4=0.0064}</annotation>

</semantics>

</math><img src="./10900181b94e3acdc027a435fd6bbe9058bd224c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:25.316ex; height:2.176ex;" alt="{\displaystyle 0.04\times 0.4\times 0.4=0.0064}" loading="lazy">. This suggests it is more likely that the patient was healthy for both of those days, rather than having a fever and recovering.

The rest of the probabilities are summarised in the following table:

<th>3

</th></tr>

<tr>

<th>Observation

</th>

<td>Normal</td>

<td>Dizzy

</td></tr>

<tr>

<th>Healthy

</th>

<td>0.00588

</td></tr>

<tr>

<th>Fever

</th>

<td>0.01512

</td></tr></tbody></table>

From the table, it can be seen that the patient most likely had a fever on the third day. Furthermore, there exists a sequence of states ending on "fever", of which the probability of producing the given observations is 0.01512. This sequence is precisely (healthy, healthy, fever), which can be found be tracing back which states were used when calculating the maxima (which happens to be the best guess from each day but will not always be). In other words, given the observed activities, the patient was most likely to have been healthy on the first day and also on the second day (despite feeling cold that day), and only to have contracted a fever on the third day.

The operation of Viterbi's algorithm can be visualized by means of a <a href="Trellis_diagram" class="mw-redirect" title="Trellis diagram">trellis diagram</a>. The Viterbi path is essentially the shortest path through this trellis.

<div class="mw-heading mw-heading2"><h2 id="Extensions">Extensions</h2></div>

A generalization of the Viterbi algorithm, termed the max-sum algorithm (or max-product algorithm) can be used to find the most likely assignment of all or some subset of <a href="Latent_variable" class="mw-redirect" title="Latent variable">latent variables</a> in a large number of <a href="Graphical_model" title="Graphical model">graphical models</a>, e.g. <a href="Bayesian_network" title="Bayesian network">Bayesian networks</a>, <a href="Markov_random_field" title="Markov random field">Markov random fields</a> and <a href="Conditional_random_field" title="Conditional random field">conditional random fields</a>. The latent variables need, in general, to be connected in a way somewhat similar to a <a href="Hidden_Markov_model" title="Hidden Markov model">hidden Markov model</a> (HMM), with a limited number of connections between variables and some type of linear structure among the variables. The general algorithm involves message passing and is substantially similar to the <a href="Belief_propagation" title="Belief propagation">belief propagation</a> algorithm (which is the generalization of the <a href="Forward-backward_algorithm" class="mw-redirect" title="Forward-backward algorithm">forward-backward algorithm</a>).

With an algorithm called <a href="Iterative_Viterbi_decoding" title="Iterative Viterbi decoding">iterative Viterbi decoding</a>, one can find the subsequence of an observation that matches best (on average) to a given hidden Markov model. This algorithm is proposed by Qi Wang et al. to deal with <a href="Turbo_code" title="Turbo code">turbo code</a>.<a href="#cite_note-9">[9]</a> Iterative Viterbi decoding works by iteratively invoking a modified Viterbi algorithm, reestimating the score for a filler until convergence.

An alternative algorithm, the Lazy Viterbi algorithm, has been proposed.<a href="#cite_note-10">[10]</a> For many applications of practical interest, under reasonable noise conditions, the lazy decoder (using Lazy Viterbi algorithm) is much faster than the original <a href="Viterbi_decoder" title="Viterbi decoder">Viterbi decoder</a> (using Viterbi algorithm). While the original Viterbi algorithm calculates every node in the <a href="Trellis_(graph)" title="Trellis (graph)">trellis</a> of possible outcomes, the Lazy Viterbi algorithm maintains a prioritized list of nodes to evaluate in order, and the number of calculations required is typically fewer (and never more) than the ordinary Viterbi algorithm for the same result. However, it is not so easy to parallelize in hardware.

<div class="mw-heading mw-heading2"><h2 id="Soft_output_Viterbi_algorithm">Soft output Viterbi algorithm</h2></div>

The soft output Viterbi algorithm (SOVA) is a variant of the classical Viterbi algorithm.

SOVA differs from the classical Viterbi algorithm in that it uses a modified path metric which takes into account the <a href="A_priori_probability" class="mw-redirect" title="A priori probability">a priori probabilities</a> of the input symbols, and produces a soft output indicating the reliability of the decision.

The first step in the SOVA is the selection of the survivor path, passing through one unique node at each time instant, t. Since each node has 2 branches converging at it (with one branch being chosen to form the Survivor Path, and the other being discarded), the difference in the branch metrics (or cost) between the chosen and discarded branches indicate the amount of error in the choice.

This cost is accumulated over the entire sliding window (usually equals at least five constraint lengths), to indicate the soft output measure of reliability of the hard bit decision of the Viterbi algorithm.

<ul><li><a href="Expectation%E2%80%93maximization_algorithm" title="Expectation–maximization algorithm">Expectation–maximization algorithm</a></li>

<li><a href="Baum%E2%80%93Welch_algorithm" title="Baum–Welch algorithm">Baum–Welch algorithm</a></li>

<li><a href="Forward-backward_algorithm" class="mw-redirect" title="Forward-backward algorithm">Forward-backward algorithm</a></li>

<li><a href="Forward_algorithm" title="Forward algorithm">Forward algorithm</a></li>

<li><a href="Error-correcting_code" class="mw-redirect" title="Error-correcting code">Error-correcting code</a></li>

<li><a href="Viterbi_decoder" title="Viterbi decoder">Viterbi decoder</a></li>

<li><a href="Hidden_Markov_model" title="Hidden Markov model">Hidden Markov model</a></li>

<li><a href="Part-of-speech_tagging" title="Part-of-speech tagging">Part-of-speech tagging</a></li>

<li><a href="A*_search_algorithm" title="A* search algorithm">A* search algorithm</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><a href="#cite_ref-1">^</a> Xavier Anguera et al., <a rel="nofollow" class="external text" href="http://www1.icsi.berkeley.edu/~vinyals/Files/taslp2011a.pdf">"Speaker Diarization: A Review of Recent Research"</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160512200056/http://www1.icsi.berkeley.edu/~vinyals/Files/taslp2011a.pdf">Archived</a> 2016-05-12 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a>, retrieved 19. August 2010, IEEE TASLP

</li>

<li id="cite_note-2"><a href="#cite_ref-2">^</a> <a rel="nofollow" class="external text" href="https://arxiv.org/abs/cs/0504020v2">29 Apr 2005, G. David Forney Jr: The Viterbi Algorithm: A Personal History</a>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFDaniel_JurafskyJames_H._Martin" class="citation book cs1">Daniel Jurafsky; James H. Martin. Speech and Language Processing. Pearson Education International. p. 246.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFSchmid2004" class="citation conference cs1">Schmid, Helmut (2004). <a rel="nofollow" class="external text" href="http://www.aclweb.org/anthology/C/C04/C04-1024.pdf">Efficient parsing of highly ambiguous context-free grammars with bit vectors</a> (PDF). Proc. 20th Int'l Conf. on Computational Linguistics (COLING). <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3115%2F1220355.1220379">10.3115/1220355.1220379</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> <cite id="CITEREFKleinManning2003" class="citation conference cs1">Klein, Dan; Manning, Christopher D. (2003). <a rel="nofollow" class="external text" href="http://ilpubs.stanford.edu:8090/532/1/2002-16.pdf">A* parsing: fast exact Viterbi parse selection</a> (PDF). Proc. 2003 Conf. of the North American Chapter of the Association for Computational Linguistics on Human Language Technology (NAACL). pp. 40–47. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.3115%2F1073445.1073461">10.3115/1073445.1073461</a>.</cite>

</li>

<li id="cite_note-6"><a href="#cite_ref-6">^</a> <cite id="CITEREFStankeKellerGunduzHayes2006" class="citation journal cs1">Stanke, M.; Keller, O.; Gunduz, I.; Hayes, A.; Waack, S.; Morgenstern, B. (2006). <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1538822">"AUGUSTUS: Ab initio prediction of alternative transcripts"</a>. Nucleic Acids Research. 34 (Web Server issue): W435 – W439. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fnar%2Fgkl200">10.1093/nar/gkl200</a>. <a href="PMC_(identifier)" class="mw-redirect" title="PMC (identifier)">PMC</a> <a rel="nofollow" class="external text" href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC1538822">1538822</a>. <a href="PMID_(identifier)" class="mw-redirect" title="PMID (identifier)">PMID</a> <a rel="nofollow" class="external text" href="https://pubmed.ncbi.nlm.nih.gov/16845043">16845043</a>.</cite>

</li>

<li id="cite_note-7"><a href="#cite_ref-7">^</a> <cite id="CITEREFQuach,_T.;_Farooq,_M.1994" class="citation conference cs1">Quach, T.; Farooq, M. (1994). "Maximum Likelihood Track Formation with the Viterbi Algorithm". Proceedings of 33rd IEEE Conference on Decision and Control. Vol. 1. pp. 271–276. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FCDC.1994.410918">10.1109/CDC.1994.410918</a>.</cite><code class="cs1-code">{{cite conference}}</code>: CS1 maint: multiple names: authors list (link)

</li>

<li id="cite_note-8"><a href="#cite_ref-8">^</a> Xing E, slide 11.

</li>

<li id="cite_note-9"><a href="#cite_ref-9">^</a> <cite id="CITEREFQi_WangLei_WeiRodney_A._Kennedy2002" class="citation journal cs1">Qi Wang; Lei Wei; Rodney A. Kennedy (2002). "Iterative Viterbi Decoding, Trellis Shaping, and Multilevel Structure for High-Rate Parity-Concatenated TCM". IEEE Transactions on Communications. 50: 48–55. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F26.975743">10.1109/26.975743</a>.</cite>

</li>

<li id="cite_note-10"><a href="#cite_ref-10">^</a> <cite class="citation conference cs1"><a rel="nofollow" class="external text" href="http://people.csail.mit.edu/jonfeld/pubs/lazyviterbi.pdf">A fast maximum-likelihood decoder for convolutional codes</a> (PDF). <a rel="nofollow" class="external text" href="http://www.ieeevtc.org/">Vehicular Technology Conference</a>. December 2002. pp. 371–375. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FVETECF.2002.1040367">10.1109/VETECF.2002.1040367</a>.</cite>

</li>

</ol></div></div>

<div class="mw-heading mw-heading2"><h2 id="General_references">General references</h2></div>

<ul><li><cite id="CITEREFViterbi_AJ1967" class="citation journal cs1">Viterbi AJ (April 1967). "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm". IEEE Transactions on Information Theory. 13 (2): 260–269. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FTIT.1967.1054010">10.1109/TIT.1967.1054010</a>.</cite> (note: the Viterbi decoding algorithm is described in section IV.) Subscription required.</li>

<li><cite id="CITEREFFeldmanAbou-FaycalFrigo2002" class="citation book cs1">Feldman J, Abou-Faycal I, Frigo M (2002). "A fast maximum-likelihood decoder for convolutional codes". Proceedings IEEE 56th Vehicular Technology Conference. Vol. 1. pp. 371–375. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.1314">10.1.1.114.1314</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FVETECF.2002.1040367">10.1109/VETECF.2002.1040367</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-7803-7467-6</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:9783963">9783963</a>.</cite></li>

<li><cite id="CITEREFForney_GD1973" class="citation journal cs1">Forney GD (March 1973). "The Viterbi algorithm". Proceedings of the IEEE. 61 (3): 268–278. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FPROC.1973.9030">10.1109/PROC.1973.9030</a>.</cite> Subscription required.</li>

<li><cite id="CITEREFPressTeukolskyVetterlingFlannery2007" class="citation book cs1">Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20110811154417/http://apps.nrbook.com/empanel/index.html#pg=850">"Section 16.2. Viterbi Decoding"</a>. Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-521-88068-8</bdi>. Archived from <a rel="nofollow" class="external text" href="http://apps.nrbook.com/empanel/index.html#pg=850">the original</a> on 2011-08-11. Retrieved 2011-08-17.</cite></li>

<li><cite id="CITEREFRabiner_LR1989" class="citation journal cs1">Rabiner LR (February 1989). "A tutorial on hidden Markov models and selected applications in speech recognition". Proceedings of the IEEE. 77 (2): 257–286. <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.381.3454">10.1.1.381.3454</a>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2F5.18626">10.1109/5.18626</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:13618539">13618539</a>.</cite> (Describes the forward algorithm and Viterbi algorithm for HMMs).</li>

<li>Shinghal, R. and <a href="Godfried_Toussaint" title="Godfried Toussaint">Godfried T. Toussaint</a>, "Experiments in text recognition with the modified Viterbi algorithm," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-l, April 1979, pp. 184–193.</li>

<li>Shinghal, R. and <a href="Godfried_Toussaint" title="Godfried Toussaint">Godfried T. Toussaint</a>, "The sensitivity of the modified Viterbi algorithm to the source statistics," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-2, March 1980, pp. 181–185.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a href="https://en.wikibooks.org/wiki/Algorithm_Implementation/Viterbi_algorithm" class="extiw external" title="b:Algorithm Implementation/Viterbi algorithm">Implementations in Java, F#, Clojure, C# on Wikibooks</a></li>

<li><a rel="nofollow" class="external text" href="http://pl91.ddns.net/viterbi/tutorial.html">Tutorial</a> on convolutional coding with viterbi decoding, by Chip Fleming</li>

<li><a rel="nofollow" class="external text" href="http://www.kanungo.com/software/hmmtut.pdf">A tutorial for a Hidden Markov Model toolkit (implemented in C) that contains a description of the Viterbi algorithm</a></li>

<li><a rel="nofollow" class="external text" href="http://www.scholarpedia.org/article/Viterbi_algorithm">Viterbi algorithm</a> by Dr. <a href="Andrew_Viterbi" title="Andrew Viterbi">Andrew J. Viterbi</a> (scholarpedia.org).</li></ul>

<div class="mw-heading mw-heading3"><h3 id="Implementations">Implementations</h3></div>

<ul><li><a rel="nofollow" class="external text" href="https://reference.wolfram.com/language/ref/FindHiddenMarkovStates.html">Mathematica</a> has an implementation as part of its support for stochastic processes</li>

<li><a rel="nofollow" class="external text" href="http://libsusa.org/">Susa</a> signal processing framework provides the C++ implementation for <a href="Forward_error_correction" class="mw-redirect" title="Forward error correction">Forward error correction</a> codes and channel equalization <a rel="nofollow" class="external text" href="https://github.com/libsusa/susa/blob/master/inc/susa/channel.h">here</a>.</li>

<li><a rel="nofollow" class="external text" href="http://www.cs.stonybrook.edu/~pfodor/viterbi/Viterbi.java">Java</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20140504055101/http://www.cs.stonybrook.edu/~pfodor/viterbi/Viterbi.java">Archived</a> 2014-05-04 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="https://juliahub.com/ui/Packages/HMMBase/8HxY5/">Julia (HMMBase.jl)</a></li>

<li><a rel="nofollow" class="external text" href="http://www.cs.stonybrook.edu/~pfodor/viterbi/viterbi.P">Prolog</a> <a rel="nofollow" class="external text" href="https://web.archive.org/web/20120502010115/http://www.cs.stonybrook.edu/~pfodor/viterbi/viterbi.P">Archived</a> 2012-05-02 at the <a href="Wayback_Machine" title="Wayback Machine">Wayback Machine</a></li>

<li><a rel="nofollow" class="external text" href="https://hackage.haskell.org/package/hmm-0.2.1.1/docs/src/Data-HMM.html#viterbi">Haskell</a></li>

<li><a rel="nofollow" class="external text" href="http://tuvalu.santafe.edu/~simon/styled-8/">SFIHMM</a> includes code for Viterbi decoding.</li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-27" href="https://en.wikipedia.org/wiki/?title=Viterbi_algorithm&oldid=1302813257">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>